#include <iostream>
#include <string>
#include <stack>
#include <vector>

using namespace std;

struct Node
{
    vector<int> next; // 连到下一个点的下标
    vector<char> id; // 该边的id

    void clear()
    {
        next.clear();
        id.clear();
    }
};

struct NodeBind
{
    int begin;
    int end;
};

Node nodes[100]{};
int count = 0;

string reversedPolishExp(string& exp);

void getNFA(const string& rp);

NodeBind connect(NodeBind a, NodeBind b); // . 前后连接

NodeBind generate(NodeBind a); // * 星闭包

NodeBind choose(NodeBind a, NodeBind b); // | 选择

int main()
{
    string exp{ "((a|b)*aa)*b" };
    string rp = reversedPolishExp(exp);
    freopen("../nfa.txt", "w", stdout); // 重定向输出
    if (rp[0] == '!') // 失败
        return -1;
    getNFA(rp);
    cout << "digraph nfa {" << endl;
    cout << '\t' << "label = \"" << exp << "\";" << endl;\
    cout << '\t' << "rankdir = LR;" << endl;
    for (int i = 1; i <= count; ++i)
        for (int j = 0; j < nodes[i].next.size(); ++j)
            if (nodes[i].next[j] != 0)
                if (nodes[i].id[j] == '$') // 为了输出好看点
                    printf("\t%d -> %d [shape = circle, label = \"%s\"];\n", i, nodes[i].next[j], "є");
                else // NOLINT
                    printf("\t%d -> %d [shape = circle, label = \"%c\"];\n", i, nodes[i].next[j], nodes[i].id[j]);
    cout << "}" << endl;
    return 0;
}


/**
 * @param exp 待转换表达式
 * @return 表达式合法则返回它的逆波兰表达式，否则返回错误信息
 * @note 转换成后缀表达式
 */
string reversedPolishExp(string& exp)
{
    struct Brackets
    {
        int symbolNum;
        int verticalNum;
    };
    // 优先级 *、+ > (、) > |
    Brackets bracket{}; // 标记一对括号括号
    stack<struct Brackets> parenStk;
    string postExpr;

    int i, len = exp.length();
    int verticalNum = 0, symbolNum = 0;

    for (i = 0; i < len; i++)
    {
        if (isspace(exp[i])) continue;
        if (isalpha(exp[i]))
        {
            if (symbolNum > 1)
            {
                symbolNum--;
                postExpr += '.';
            }
            symbolNum++;
            postExpr += exp[i];
        }
        else if (exp[i] == '(')
        {
            if (symbolNum > 1)
                postExpr += '.';
            bracket.symbolNum = symbolNum;
            bracket.verticalNum = verticalNum;
            parenStk.push(bracket);
            verticalNum = 0;
            symbolNum = 0;
        }
        else if (exp[i] == ')')
        {
            if (symbolNum == 0 || parenStk.empty())
                return "!ILLEGAL Regex Expression: Bracket Not Match";
            while (--symbolNum > 0) //比如((a|b)(c|d))模式，当上一次匹配完倒数第二个右括号后，symbolNum为2，需要添加'.'
                postExpr += '.';
            while (verticalNum-- > 0)
                postExpr += '|';
            bracket = parenStk.top();
            parenStk.pop();
            symbolNum = bracket.symbolNum;
            verticalNum = bracket.verticalNum;
            symbolNum++;
        }
        else if (exp[i] == '*')
        {
            if (symbolNum == 0)
                return "!ILLEGAL Regex Expression: Illegal Appearance of '*'";
            postExpr += exp[i];
        }
        else if (exp[i] == '|')
        {
            if (symbolNum == 0)
                return "!ILLEGAL Regex Expression: Illegal Appearance of '|'";
            while (--symbolNum > 0)
                postExpr += '.';
            verticalNum++;
        }
        else
            return "!ILLEGAL Regex Expression.";
    }
    if (!parenStk.empty())
        return "!ILLEGAL Regex Expression: Bracket Not Match";

    while (--symbolNum > 0)
        postExpr += '.';

    while (verticalNum-- > 0) // 输出优先级最低的 |
        postExpr += '|';

    return postExpr;
}

/**
 * @param rp 要转换成NFA的正规式的后缀表达式
 * @note 把转换成后缀表达式的正规式转成nfa存入nodes数组
 */
void getNFA(const string& rp)
{
    stack<NodeBind> edgeStack;
    for (char c : rp) // 构建NFA
    {
        if (isalpha(c) || isdigit(c))
        {
            NodeBind temp{};
            temp.begin = ++count;
            temp.end = ++count;
            nodes[temp.begin].next.push_back(temp.end);
            nodes[temp.begin].id.push_back(c);
            edgeStack.push(temp);
        }
        else
        {
            if (c == '.')
            {
                NodeBind temp1 = edgeStack.top();
                edgeStack.pop();
                NodeBind temp2 = edgeStack.top();
                edgeStack.pop();
                NodeBind temp = connect(temp2, temp1);
                edgeStack.push(temp);
            }
            else if (c == '|')
            {
                NodeBind temp1 = edgeStack.top();
                edgeStack.pop();
                NodeBind temp2 = edgeStack.top();
                edgeStack.pop();
                NodeBind temp = choose(temp2, temp1);
                edgeStack.push(temp);
            }
            else if (c == '*')
            {
                NodeBind temp1 = edgeStack.top();
                edgeStack.pop();
                NodeBind temp = generate(temp1);
                edgeStack.push(temp);
            }
        }
    }
}

NodeBind connect(NodeBind a, NodeBind b)
{
    NodeBind temp{};
    temp.begin = a.begin;
    nodes[a.end] = nodes[b.begin];
    nodes[b.begin].clear();
    temp.end = b.end;
    return temp;
}

NodeBind generate(NodeBind a)
{
    NodeBind temp{};
    temp.begin = ++count;
    nodes[count].next.push_back(a.begin);
    nodes[count].next.push_back(temp.begin + 1);

    nodes[count].id.push_back('$');
    nodes[count].id.push_back('$');

    nodes[a.end].next.push_back(a.begin);
    nodes[a.end].id.push_back('$');
    temp.end = ++count;

    nodes[a.end].next.push_back(count);
    nodes[a.end].id.push_back('$');
    return temp;
}

NodeBind choose(NodeBind a, NodeBind b)
{
    NodeBind temp{};
    temp.begin = ++count;

    nodes[count].next.push_back(a.begin);
    nodes[count].next.push_back(b.begin);

    nodes[count].id.push_back('$');
    nodes[count].id.push_back('$');

    temp.end = ++count;

    nodes[a.end].next.push_back(count);
    nodes[b.end].next.push_back(count);

    nodes[a.end].id.push_back('$');
    nodes[b.end].id.push_back('$');
    return temp;
}